package com.leetcode.dp;

/**
 * @author Dennis Li
 * @date 2020/7/20 9:58
 */
public class WiggleMaxLength_376 {

    // 最长子序列的核心，dp是以第n为结尾的状态
    public int wiggleMaxLength(int[] nums) {
        int len = nums.length;
        if (len < 2) return len;
        int[] up = new int[len];
        int[] down = new int[len];
        for (int i = 1; i < len; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if(nums[i] > nums[j])
                    up[i] = Math.max(up[i], down[j] + 1);
                else if(nums[i] < nums[j])
                    down[i] = Math.max(down[i], up[j] + 1);
            }
        }
        return 1 + Math.max(down[len - 1], up[len - 1]);
    }

    public int wiggleMaxLength2(int[] nums) {
        if (nums.length < 2)
            return nums.length;
        int down = 1, up = 1;
        // 节省空间，并且发现摆荡规律可以线性化
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1])
                up = down + 1;
            else if (nums[i] < nums[i - 1])
                down = up + 1;
        }
        return Math.max(down, up);
    }

}
